1. Field of the Invention
The present invention relates to an error correcting code decoding device, a program and a method used therein and more particularly to an error correcting code decoding device, a program and a method used therein for a Low-Density Parity-Check Code (hereinafter referred to as LDPC code).
2. Description of the Related Art
The error correcting code is a technique for reducing noise effects during data transmission by such processing as coding or decoding. Coding is a process of adding redundancy to data to be transmitted. The coded data is called a codeword. A codeword sent into a communication channel is affected by noise, resulting in such an error as having some bits reversed when the codeword is received. Decoding is a process of recovering data from such an error-ridden received word by using redundancy.
A LDPC code is an error correcting code proposed in 1960s. The LDPC code had not drawn attention until late 1990s, when a relation between the LDPC code and the Turbo code was pointed out. (For example, see Non-Patent Document 1)
Non-Patent Document 1: D. J. C. Macky and R. M. Neal, “Good error correcting codes based on very sparse matrices,” IEEE Transactions on Information Theory 45 pp. 399-431, 1999.
For an error correcting code, a decoding process, which is typically an estimation process, is more complicated than a coding process. Particularly, in order to provide maximum likelihood decoding or a decoding performance near to that on a code of high error-correction performance with a long code length, a decoding process needs to take on extremely high complexity.
A LDPC code features a parity check matrix with an extreme number of 0s. This feature enables relatively effective high-performance decoding method, which is called Message-Passing decoding (hereinafter referred to as MP decoding).
Now, MP decoding on a LDPC code will be described. For simplicity, it is assumed that a code is a binary, and a modulation system is BPSK, in which a soft decision value of +1 for bit 0 of a codeword or −1 for bit 1 in the case of no error would be a received value.
MP decoding on a LDPC code will be described by using a bipartite graph, which is called Tanner graph corresponding to a parity check matrix. FIGS. 14A and 14B show examples of parity check matrix H and its corresponding Tanner graph G, respectively.
Nodes on Tanner graph G are classified into two types; variable nodes and check nodes. A variable node corresponds to a column of matrix H, i.e., codeword bit, while a check node corresponds to a row of matrix H. By connecting between nodes on Tanner graph G whose cross point on matrix H is filled with 1 by an edge, a graph for the matrix H is made, which is called Tanner graph corresponding to matrix H.
Decoding method on a LDPC code is performed by repeatedly updating a quantity called “message” assigned to an edge of a graph on a node. A message has two types; a message from a check node to a variable node and a message from a variable node to a check node. Each type of message corresponds to reliability information on a codeword bit calculated at a node.
A number of methods are known for an algorithm at a variable node and a check node.
One of the methods with the most efficient decoding feature is sum-product algorithm. A method called the min-sum algorithm with relatively low complexity is described here.
It is assumed that a received value of a codeword bit corresponding to a certain valuable node is r, and a message from a checknode to this variable node is c(1), (2), . . . , c(d_v) (d_v is a number of edges coming out from the variable node). The variable node sends out v(1), which is expressed in [expression 1], to a check node at the other end of a corresponding edge.v(1)←r+c(2)+ . . . +c(d_v)  [expression 1]v(i) (i=2, . . . , d) is also obtained as a sum of r and c(j) (j≠i).
When it is assumed that a message to a certain check node is v(1), . . . , v(d_c) (d_c is a number of edges coming out from the check node), the check node sends out c(1), which is expressed in [expression 2], to a variable node at the other end of corresponding edge.c(1)←sgn(v(2), . . . ,v(d_c))·min{|v(2)|, . . . ,|v(d_c)|}  [expression 2]where sgn(v(2), . . . , v(d_c)) is a value of v(i) (i=2, . . . , d_c) multiplied by a sign (+1 or −1), |a| is an absolute value of a, and min is a function for selecting the minimum value.
c(i)(i=2, . . . ,d) is also obtained by using v(j) (j≠i).
A LDPC code has a small number of edges for each node. Thus, [expression 1] and [expression 2] can be processed with low complexity.
Here we call a processing unit performing [expression 1] and [expression 2] once for all nodes “1 iteration process”. MP decoding is accomplished by repeating this literation process. The number to be repeated is generally around 10 to 30.
The final decision of 0 and 1 (hard decision) is performed by deciding whether [expression 3] is positive or negative at each codeword bit.r+c(1)+ . . . +c(d_v)  [expression 3]
When a result of the hard decision for each of all the check nodes is obtained, iteration process of MP decoding finishes.
If the entire graph G can be embodied in a device, the processes are expected to be speedier, which is difficult because a LDPC code is generally used in a long code length (1000-). Therefore, a message is stored in memory, some of the graph G nodes are operated in parallel by sharing a circuit so that complexity and throughput of a device is adjusted.
There is a coding scheme design for designing a decoder that runs partly in parallel at first to follow the above mentioned line and form an appropriate code for the decoder (for example, see Non-Patent Document 2).
Non-Patent Document 2: E. Bautillon, J. Castura, and F. R. Kschischang, “Decoder-First Code Design”, the 2nd Internatinal Symposium on Turbo Codes and Related Topics, pp. 459-462, 2000.
FIG. 15 is a block diagram of decoder disclosed in Non-Patent Document 2.
The decoder of FIG. 15 will be described.
Memory means 1501 holds a received value and a message c(i) of [expression 2]. The decoder of FIG. 15 has a plurality of this memory means.
Address generation means 1502 generates an address to access memory means 1501, corresponding one-to-one with memory means 1501.
Variable node function means 1503 is a circuit to process [expression 1], corresponding one-to-one with memory means 1501.
Check node function means 1504 is a circuit to process [expression 2]. The number of inputs and outputs corresponds to the number of edges of a check node in Tanner graph.
Shuffle network means 1505 determines the connection between variable node function means 1503 and check node function means 1504.
In this decoder, respective variable node function means 1503 corresponds one-to-one with memory means 1501 so that they can operate in parallel without any collision between accesses to memory means 1501.
In addition, all the inputs to respective check node functions can be obtained concurrently on this occasion so that check node function means 1505 can also operate in parallel.
In this manner, a partially parallel process can be effectively provided with the decoder of FIG. 15.
However, the decoder of FIG. 15 has not had its configuration optimized, remaining to be simplified further. In optimizing the decoder, care must be taken to avoid degradation of coding performance.
Non-Patent Document 2 does not specifically mention how to give address generation means and shuffle network means.
Moreover, in the configuration of FIG. 15, a shuffle network permutates all the output from variable node function means. That can cause a schedule controlling processes to be complicated when a smaller part operates in parallel in order to meet resource on implementation.